package genetic.q1;


import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Vector;

public abstract class Phenotype {

	public abstract double fitness(Genotype g);
	public abstract Genotype createRandomInstance();
	public abstract Genotype[] crossover(Genotype g1, Genotype g2);
	public abstract Genotype mutate(Genotype g, double Pm);
	public abstract List<Genotype> getMatingPool(List<Genotype> population, int populationSize);
	public abstract void updateFitness(List<Genotype> population);
	public abstract List<Genotype> getInitialPopulation(int populationSize);

	public List<Genotype> getInitialRandomPopulation(int size){
		List<Genotype> population = new LinkedList<Genotype>();
		for (int i = 0; i < size; i++) {
			population.add(createRandomInstance());
		}
		return population;
	}

	public int[] getRandomIntString(int size, int min, int max){
		int[] ans = new int[size];
		for (int i=0; i<size; i++){
			ans[i] = (int)(Math.random()*(max-min+1)+min);
		}
		return ans;
	}

	public int[][] crossover1(int[] org1, int[] org2){
		int[][] res = new int[2][org1.length];
		for (int i=0; i<org1.length; i++){
			if (Math.random() < 0.5){
				res[0][i] = org1[i];
				res[1][i] = org2[i];
			} else {
				res[0][i] = org2[i];
				res[1][i] = org1[i];
			}
		}
		return res;
	}

	public int[][] crossover2(int[] org1, int[] org2, int interval){
		int[][] res = new int[2][org1.length];
		for (int i=0; i<org1.length; i++){
			if ((i / interval) % 2 == 0){
				res[0][i] = org1[i];
				res[1][i] = org2[i];
			} else {
				res[0][i] = org2[i];
				res[1][i] = org1[i];
			}
		}
		return res;
	}

	public int[] mutation(int[] org, double Pr, int min, int max){
		int[] ans = Arrays.copyOf(org, org.length);
		for (int i=0; i<org.length; i++){
			if (Math.random()<Pr){
				ans[i] = (int)(Math.random()*(max-min+1)+min); 
			}
		}
		return ans;
	}


	protected List<Genotype> getMatingPoolRouletteWheel(List<Genotype> population, int populationSize){	
		List<Genotype> matingPool = new LinkedList<Genotype>();

		double fitnessSum = 0;
		for (Genotype g: population){
			fitnessSum = fitnessSum + fitness(g);
		}
		for (int i=0; i<populationSize; i++){	//creating the mating pool
			double rand = Math.random()*fitnessSum;
			for (Genotype g: population){
				rand = rand - fitness(g);
				if (rand<=0){
					matingPool.add(g);
					break;
				}
			}
		}
		Collections.shuffle(matingPool);
		return matingPool;
	}

	protected List<Genotype> getMatingPoolTournamentSelection(List<Genotype> population, int populationSize, int tournamentSize, int numWinners, double p){	
		List<Genotype> matingPool = new LinkedList<Genotype>();

		while (matingPool.size()<populationSize){
			Vector<Genotype> tournament = new Vector<Genotype>();
			for (int i=0; i<tournamentSize; i++){
				int index = (int)(Math.random()*(double)populationSize);
				tournament.add(population.get(index));
			}

			Collections.sort(tournament, new Comparator<Genotype>(){
				@Override
				public int compare(Genotype o1, Genotype o2) {
					if (fitness(o1) > fitness(o2)){
						return -1;
					} else if (fitness(o1) < fitness(o2)){
						return 1;
					} else {
						return 0;
					}
				}
			});

			for (int i=0; i<numWinners; i++){
				for (int j=0; j<tournament.size(); j++){
					if (Math.random()<p || j == tournament.size()-1){
						matingPool.add(tournament.remove(j));
						break;
					}
				}
			}
		}
		Collections.shuffle(matingPool);
		return matingPool;
	}

	public List<Genotype> elitist(List<Genotype> population,
			int populationSize, int elitism) {
		List<Genotype> ans = new LinkedList<Genotype>();

		double[][] tmp = new double[populationSize][2];
		for(int i=0; i<populationSize; i++){
			tmp[i][0]=i;
			tmp[i][1]=fitness(population.get(i));
		}
		mergeSort(tmp);
		for(int i=0; i<elitism; i++){
			Genotype g = population.get((int)tmp[tmp.length-(1+i)][0]).clone();
			ans.add(g);
		}
		return ans;
	}

	/**
	 * Mergesort algorithm.
	 * @param a an array of Comparable items.
	 */
	public static void mergeSort( double [][] a ) {
		double [][] tmpArray = new double[ a.length ][2];
		mergeSort( a, tmpArray, 0, a.length - 1 );
	}

	/**
	 * Internal method that makes recursive calls.
	 * @param a an array of Comparable items.
	 * @param tmpArray an array to place the merged result.
	 * @param left the left-most index of the subarray.
	 * @param right the right-most index of the subarray.
	 */
	private static void mergeSort( double [][] a, double [][] tmpArray,
			int left, int right ) {
		if( left < right ) {
			int center = ( left + right ) / 2;
			mergeSort( a, tmpArray, left, center );
			mergeSort( a, tmpArray, center + 1, right );
			merge( a, tmpArray, left, center + 1, right );
		}
	}

	/**
	 * Internal method that merges two sorted halves of a subarray.
	 * @param a an array of Comparable items.
	 * @param tmpArray an array to place the merged result.
	 * @param leftPos the left-most index of the subarray.
	 * @param rightPos the index of the start of the second half.
	 * @param rightEnd the right-most index of the subarray.
	 */
	private static void merge( double [][] a, double [][] tmpArray,
			int leftPos, int rightPos, int rightEnd ) {
		int leftEnd = rightPos - 1;
		int tmpPos = leftPos;
		int numElements = rightEnd - leftPos + 1;

		// Main loop
		while( leftPos <= leftEnd && rightPos <= rightEnd )
			if( a[leftPos][1]< a[rightPos][1] ){
				tmpArray[tmpPos][0] = a[leftPos][0];
				tmpArray[tmpPos][1] = a[leftPos][1];
				tmpPos++;
				leftPos++;
			}
			else{
				tmpArray[tmpPos][0] = a[rightPos][0];
				tmpArray[tmpPos][1] = a[rightPos][1];
				tmpPos++;
				rightPos++;
			}
		while( leftPos <= leftEnd ){    // Copy rest of first half
			tmpArray[ tmpPos ][0] = a[ leftPos ][0];
			tmpArray[ tmpPos ][1] = a[ leftPos ][1];
			tmpPos++;
			leftPos++;
		}
		while( rightPos <= rightEnd ){  // Copy rest of right half
			tmpArray[ tmpPos ][0] = a[ rightPos ][0];
			tmpArray[ tmpPos ][1] = a[ rightPos ][1];
			tmpPos++;
			rightPos++;
		}
		// Copy tmpArray back
		for( int i = 0; i < numElements; i++, rightEnd-- ){
			a[ rightEnd ][0] = tmpArray[ rightEnd ][0];
			a[ rightEnd ][1] = tmpArray[ rightEnd ][1];
		}
	}

}
